package main.面试金典第六版;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class Interview03 {
    public static void main(String[] args) {
        System.out.println("面试题03.01：三合一");
        System.out.println("面试题03.02：栈的最小值");
        System.out.println("面试题03.03：堆盘子");
        System.out.println("面试题03.04：化栈为队");
        System.out.println("面试题03.05：栈排序");
        System.out.println("面试题03.06：动物收容所");
    }
}

class Interview_03_01{
    int N = 3;
    int[][] data;
    int[] locations;

    public Interview_03_01(int stackSize) {
        data = new int[N][stackSize];
        locations = new int[N];
    }

    public void push(int stackNum, int value) {
        int[] stk = data[stackNum];
        int loc = locations[stackNum];
        if (loc < stk.length) {
            stk[loc] = value;
            locations[stackNum]++;
        }
    }

    public int pop(int stackNum) {
        int[] stk = data[stackNum];
        int loc = locations[stackNum];
        if (loc > 0) {
            int val = stk[loc - 1];
            locations[stackNum]--;
            return val;
        }
        else return -1;
    }

    public int peek(int stackNum) {
        int[] stk = data[stackNum];
        int loc = locations[stackNum];
        if (loc > 0) return stk[loc - 1];
        else return -1;
    }

    public boolean isEmpty(int stackNum) {
        return locations[stackNum] == 0;
    }
}

class Interview_03_02{
    Stack<Integer> stack,assStack;
    public Interview_03_02() {
        stack=new Stack<>();
        assStack=new Stack<>();
        assStack.push(Integer.MAX_VALUE);
    }

    public void push(int x) {
        stack.push(x);
        if (x<assStack.peek()) {
            assStack.push(x);
        }else {
            assStack.push(assStack.peek());
        }
    }

    public void pop() {
        stack.pop();
        assStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return assStack.peek();
    }
}

class Interview_03_03{
    List<Stack<Integer>> stacks;
    int cap;
    Stack<Integer> curStack;
    public Interview_03_03(int cap) {
        this.cap=cap;
        stacks=new ArrayList<>();
    }

    public void push(int val) {
        if (cap == 0) return;
        if (stacks.isEmpty()) stacks.add(new Stack<>());
        if (stacks.get(stacks.size() - 1).size() == cap) stacks.add(new Stack<>());
        stacks.get(stacks.size() - 1).push(val);
    }

    public int pop() {
        return popAt(stacks.size() - 1);
    }

    public int popAt(int index) {
        if (cap == 0 || index < 0 || index >= stacks.size()) return -1;
        int pop = stacks.get(index).pop();
        if (stacks.get(index).empty()) stacks.remove(index);
        return pop;
    }
}

class Interview_03_04{
    Stack<Integer> stack1,stack2;
    /** Initialize your data structure here. */
    public Interview_03_04() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        stack1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        while (stack1.size()>1) {
            Integer pop = stack1.pop();
            stack2.push(pop);
        }
        int result=stack1.pop();
        while (!stack2.isEmpty()) {
            Integer pop = stack2.pop();
            stack1.push(pop);
        }
        return result;
    }

    /** Get the front element. */
    public int peek() {
        while (stack1.size()>1) {
            Integer pop = stack1.pop();
            stack2.push(pop);
        }
        int result=stack1.peek();
        while (!stack2.isEmpty()) {
            Integer pop = stack2.pop();
            stack1.push(pop);
        }
        return result;
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack1.empty();
    }
}

class Interview_03_05{
    Stack<Integer> sortStack,assStack;
    public Interview_03_05() {
        sortStack=new Stack<>();
        assStack=new Stack<>();
    }

    public void push(int val) {
        while (!sortStack.isEmpty()&&val>sortStack.peek()) {
            Integer pop = sortStack.pop();
            assStack.push(pop);
        }
        sortStack.push(val);
        while (!assStack.isEmpty()) {
            Integer pop = assStack.pop();
            sortStack.push(pop);
        }
    }

    public void pop() {
        if (!sortStack.isEmpty()) sortStack.pop();
    }

    public int peek() {
        if (sortStack.isEmpty()) return -1;
        else return sortStack.peek();
    }

    public boolean isEmpty() {
        return sortStack.isEmpty();
    }
}

class Interview_03_06{
    LinkedList<int[]> queue;

    public Interview_03_06() {
        queue = new LinkedList<>();
    }

    public void enqueue(int[] animal) {
        queue.offer(animal);
    }

    public int[] dequeueAny() {
        return queue.isEmpty() ? new int[] {-1, -1} : queue.poll();
    }

    public int[] dequeueDog() {
        int[] dog = {-1, -1};
        for (int[] ani : queue) {
            if (ani[1] == 1) {
                dog = ani;
                break;
            }
        }
        queue.remove(dog);
        return dog;
    }

    public int[] dequeueCat() {
        int[] cat = {-1, -1};
        for (int[] ani : queue) {
            if (ani[1] == 0) {
                cat = ani;
                break;
            }
        }
        queue.remove(cat);
        return cat;
    }
}